package com.hqq.exercise.array;

/**
 * NumWithSum 和为s的两个数字
 * 题目描述:
 * 输一个递增排序的数组和一个数字s,在数组中查找两个数使得它们的和正好是s。如果有多对数字的和等于s，输出任意一对即可
 * 样例输入:
 * {1,2,4,7,11,15},15
 * 样例输出:
 * {4,11}
 * 思路:
 * 根据数组的递增有序的
 * 可以使用两个指针 一个指向最小 一个指向最大的数
 * 如果两个数的和 = 目标数 找到
 * 如果两个数的和 > 目标数 右指针递减
 * 如果两个数的和 < 目标数 左指针递增
 * 总结:
 * 对于递增数组求和问题 可以考虑双指针
 * Created by heqianqian on 2017/8/23.
 */
public class NumWithSum {

    public static int[] sumNum(int[] array, int sum) {
        if (array == null || array.length == 0) {
            return null;
        }
        int[] pairs = new int[2];
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if (array[i] + array[j] == sum) {
                    pairs[0] = array[i];
                    pairs[1] = array[j];
                    return pairs;
                }
            }
        }
        return null;
    }

    public static int[] sumNumOptimized(int[] array, int sum) {
        if (array == null || array.length == 0) {
            return null;
        }
        int[] pairs = new int[2];
        int left = 0;
        int right = array.length - 1;
        while (left < right) {
            if (array[left] + array[right] == sum) {
                pairs[0] = array[left];
                pairs[1] = array[right];
                return pairs;
            }
            while (left < right && (array[left] + array[right]) > sum) {
                right--;
            }
            while (left < right && (array[left] + array[right]) < sum) {
                left++;
            }
        }
        return null;
    }

}
